package com.leetcode.amazon;

import com.leetcode.library.TreeNode;

/**
 * Created by liwentian on 17/8/9.
 */

public class LowestCommonAncestorOfABinaryTree {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null) {
            return right != null ? root : left;
        } else {
            return right;
        }
    }
}
